package com.BXuan.LeetCode.数组.数组_双指针;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
/**
 * 双指针技巧秒杀数组题目
 */
public class Solution {
    public static void main(String[] args) {

    }
    /**
     * 167.两数之和ii-输入有序数组 》 快慢指针
     * https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
     */
    public static int[] twoSum(int[] numbers, int target) {
        //以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
        int[] result = new int[2];
        int slow,fast = 0;

        for (slow = 0; slow < numbers.length; slow++){
            fast = slow + 1;
            while(fast < numbers.length){
                if (numbers[slow] + numbers[fast] == target){
                    result[0] = slow + 1;
                    result[1] = fast + 1;
                    return result;
                }
                fast++;
            }
        }
        return result;
    }
    /**
     * 26.删除有序数组中的重复项 》 快慢指针
     */
    public int removeDuplicates(int[] nums) {
        int slow = 0, fast;
        for (fast = 0; fast < nums.length; fast++){
            if (nums[slow] != nums[fast]){
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
    /**
     * 27. 移除元素 》 快慢指针
     */
    public int removeElement(int[] nums, int val) {
        int slow = 0, fast = 0;
        while (fast < nums.length){
            if (nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
    /**
     * 283. 移动零 》 快慢指针
     */
    public void moveZeroes(int[] nums) {
        int slow = 0, fast = 0;
        while (fast < nums.length){
            if (nums[fast] != 0){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        while (slow < nums.length){
            nums[slow] = 0;
            slow++;
        }
    }
    /**
     * 344. 反转字符串 》 左右指针
     */
    public void reverseString(char[] s) {
        int left = 0, right = s.length-1;
        while (left < right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
    /**
     * 5.最长回文字串
     * 首先要清楚，如何找到一个回文字符。
     * 要是简单的判断该字符串是否是回文子串，那么直接从左右开始进行遍历即可。
     * 但是要判断一个字符串里面的最长回文子串，那么就得对该字符串中的每一个字符进行左右的遍历
     * 直至找出最长回文子串。
     * 寻找回文子串的方法也是从中间向两边开始扩散，此时应该考虑两种情况，奇数与偶数。
     */
    public String longestPalindrome(String s) {
        String res = "";
        // 对字符串进行遍历，并且对每一个字符进行最长回文子串判断
        for (int i = 0; i < s.length(); i++){
            String s1 = findString(i, i, s);
            String s2 = findString(i, i+1, s);
            res = res.length() > s1.length()? res : s1;
            res = res.length() > s2.length()? res : s2;
        }
        return res;
    }
    // 寻找回文子串方法
    public String findString(int left, int right, String s){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return s.substring(left+1, right);
    }
    /**
     * 83.删除排序链表中的重复元素
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast.next != null){
            if (fast.val == slow.val){
                slow.next = fast.next;
                fast = fast.next;
            }else {
                slow = fast;
                fast = fast.next;
            }
        }
        if (fast.val == slow.val){
            slow.next = null;
        }
        return head;
    }
    /**
     * 剑指 Offer 57.和为s的两个数
     */
    public int[] twoSum02(int[] nums, int target) {
        int[] result = new int[2];
        // 左右指针
        int left = 0, right = nums.length - 1;
        while (left < right){
            if (nums[left] + nums[right] == target){
                result[0] = nums[left];
                result[1] = nums[right];
                return result;
            }else if (nums[left] + nums[right] < target){
                left++;
            }else {
                right--;
            }
        }
        return result;
    }
    /**
     * 剑指 Offer II 006. 排序数组中两个数字之和
     */
    public int[] twoSum03(int[] numbers, int target) {
        int[] res = new int[2];
        int fast = 0;

        for (int slow = 0; slow < numbers.length; slow++){
            fast = slow + 1;
            while (fast < numbers.length){
                if (numbers[slow] + numbers[fast] == target){
                    res[0] = slow;
                    res[1] = fast;
                    return res;
                }
                fast++;
            }
        }
        return res;
    }
}
